package tx.algoritmiek.week2;

public class QuickSortAlgorithm {

    private GameObject[] gameObjects;
    private SplitNode root;

    /**
     * Sorts the given GameObject array using the quicksort algorithm.
     * 
     * @param gameObjects
     *            The objects to sort.
     * @return Sorted array.
     */
    public Node sortGameObjects(GameObject[] gameObjects) {
        this.gameObjects = gameObjects;

        if(this.gameObjects.length <= 1) {
            if(this.gameObjects.length == 1)
                return new EndNode(null, gameObjects[0]);
        } else {
            root = new SplitNode(null);
            quickSort(root, 0, 0, gameObjects.length-1);
        }

        return root;
    }

    /**
     * Sorts the object-array field.
     * 
     * @param coordinate
     *            Determines which axis the current sort iteration is on: 0 for
     *            X, 1 for Y.
     * @param left
     *            Index of the left value.
     * @param right
     *            Index of the right value.
     */
    private void quickSort(SplitNode splitNode, int coordinate, int left, int right) {
        if(right - left <= 1) {
            if(right-left == 1) {
                if(gameObjects[left].getPosition(coordinate) 
                        > gameObjects[right].getPosition(coordinate)) {
                    swap(left, right);
                }
                splitNode.setLeftChild(new EndNode(splitNode, gameObjects[left]));
                splitNode.setRightChild(new EndNode(splitNode, gameObjects[right]));
            } else {
                SplitNode temp = splitNode.getParent();
                if(temp.getLeftChild().equals(splitNode)) {
                    temp.setLeftChild(new EndNode(splitNode, gameObjects[left]));
                } else {
                    temp.setRightChild(new EndNode(splitNode, gameObjects[left]));
                }
            }
        } else { 
            double pivot = getPivot(coordinate, left, right);
            int middle = partitioning(coordinate, pivot, left, right);

            SplitNode leftSplit = new SplitNode(splitNode);
            splitNode.setLeftChild(leftSplit);
            SplitNode rightSplit = new SplitNode(splitNode);
            splitNode.setRightChild(rightSplit);

            quickSort(leftSplit, (coordinate+1) % 2, left, middle-1);
            quickSort(rightSplit, (coordinate+1) % 2, middle, right);
        }
    }

    /**
     * Gets the pivot for the current sort iteration.
     * 
     * @param coordinate
     *            Determines which axis the current sort iteration is on: 0 for
     *            X, 1 for Y.
     * @param left
     * @param right
     * @return Pivot value for the given coordinate.
     */
    private double getPivot(int coordinate, int left, int right) {
        int middle = (left + right) / 2;
        if (gameObjects[left].getPosition(coordinate) > gameObjects[middle]
                                                                    .getPosition(coordinate)) {
            swap(left, middle);
        }

        if (gameObjects[left].getPosition(coordinate) > gameObjects[right]
                                                                    .getPosition(coordinate)) {
            swap(left, right);
        }

        if (gameObjects[middle].getPosition(coordinate) > gameObjects[right]
                                                                      .getPosition(coordinate)) {
            swap(middle, right);
        }

        swap(middle, right - 1);

        return gameObjects[right - 1].getPosition(coordinate);
    }

    private int partitioning(int coordinate, double pivot, int left, int right) {
        int leftScan = left;
        int rightScan = right - 1;

        while (true) {
            while (gameObjects[++leftScan].getPosition(coordinate) < pivot)
                ;

            while (gameObjects[--rightScan].getPosition(coordinate) > pivot)
                ;

            if (leftScan < rightScan) {
                swap(leftScan, rightScan);
            } else {
                break;
            }
        }

        swap(leftScan, right - 1); // Swap back pivot
        return leftScan; // return pivot
    }

    /**
     * Swaps the values of the given parameters.
     * 
     * @param index1
     * @param index2
     */
    private void swap(int index1, int index2) {
        GameObject temp = gameObjects[index1];
        gameObjects[index1] = gameObjects[index2];
        gameObjects[index2] = temp;
    }
}
